googologywikiaorg-20200223-history
Veblen function
The Veblen functions are a hierarchy of normal functions \(\varphi_\alpha: \textrm{On} \rightarrow \textrm{On}\) on \(\textrm{On}\), proposed by american mathematician Oswald Veblen in his article "Continuous Increasing Functions of Finite and Transfinite Ordinals" in 1908. This allows to obtain ordinals beyond limit of the Cantor normal form. The modern version of the Veblen function is described below. The Veblen hierarchy The hierarchy is defined as follows: 1) \(\varphi_0(\gamma)=\omega^\gamma\) 2) For \(\alpha>0\), \(\varphi_\alpha(\gamma)=\) the \(1+\gamma\)th common fixed point of the functions \(\varphi_\beta(\xi)=\xi\) for all \(\beta<\alpha\). Thus \(\varphi_1(\gamma)=\varepsilon_\gamma\), \(\varphi_2(\gamma)=\zeta_\gamma\) and so on (\(\varepsilon_\gamma\) enumerates the ordinals \(\xi\) such that \(\xi = \omega^\xi\) and \(\zeta_\gamma\) enumerates the ordinals \(\xi\) such that \(\xi = \varepsilon_\xi\) ). For example: \(\varphi_2(2)=\zeta_2\) is common fixed point of the functions \(\varphi_0(\xi)=\xi\) and \(\varphi_1(\xi)=\xi\) so far as \(\zeta_2=\omega^{\zeta_2}\) as well as \(\zeta_2=\varepsilon_{\zeta_2}\) and this is third common fixed point for this functions after \(\zeta_0\) and \(\zeta_1\). Every non-zero ordinal \(\alpha<\Gamma_0\) can be uniquely written in normal form for the Veblen hierarchy: \(\alpha=\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)\), where * \(\varphi_{\beta_1}(\gamma_1) \ge \varphi_{\beta_2}(\gamma_2) \ge \cdots \ge \varphi_{\beta_k}(\gamma_k)\) * \(\gamma_m < \varphi_{\beta_m}(\gamma_m)\) for \(m \in \{1,...,k\}\) Note: \(\Gamma_0\) is the smallest ordinal \(\alpha\) such that \(\varphi_\alpha(0)=\alpha\). Fundamental sequences for the Veblen hierarchy Fundamental sequence for a limit ordinal \(\alpha\) is a strictly increasing sequence which has the ordinal \(\alpha\) as its limit. Below \(\alphan\) denotes the n''-th element of the fundamental sequence assigned to the limit ordinal \(\alpha\), where \(n\) is a non-negative integer. Fundamental sequences for the Veblen's hierarchy are defined as follows: For limit ordinals \(\alpha<\Gamma_0\), written in normal form for the Veblen hierarchy 1.1) \((\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k))n=\varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + \varphi_{\beta_k}(\gamma_k) n\), 1.2) \(\varphi_0(\gamma)=\omega^{\gamma}\) and \(\varphi_0(\gamma+1) n = \omega^{\gamma} \cdot n\), 1.3) \(\varphi_{\beta+1}(0)n=\varphi_{\beta}^n(0)\), 1.4) \(\varphi_{\beta+1}(\gamma+1)n=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1)\), 1.5) \(\varphi_{\beta}(\gamma) n = \varphi_{\beta}(\gamma n)\) for a limit ordinal \(\gamma<\varphi_\beta(\gamma)\), 1.6) \(\varphi_{\beta}(0) n = \varphi_{\beta n}(0)\) for a limit ordinal \(\beta<\varphi_\beta(0)\), 1.7) \(\varphi_{\beta}(\gamma+1) n = \varphi_{\beta n}(\varphi_{\beta}(\gamma)+1)\) for a limit ordinal \(\beta\). In rules 1.3 and 1.4, \(\varphi^n\) denotes function iteration: \(\varphi_{\beta}^0(\gamma)=\gamma\) and \(\varphi_{\beta}^{m+1}(\gamma)=\varphi_{\beta}(\varphi_{\beta}^{m}(\gamma))\). The extended (finitary) Veblen function For the building of Veblen function with arbitrary amount of arguments, let's consider \(\varphi_\alpha(\gamma)\) as binary function \(\varphi(\alpha, \gamma)\). Let ''z be an empty string or a string with one or more zeros \(0,0,...,0\) and s'' be an empty string or an arbitrary string of ordinal variables \(\alpha_1, \alpha_2,...,\alpha_n\) with \(\alpha_1>0\). The binary function \(\varphi(\alpha, \gamma)\) can be written as \(\varphi(s,\alpha, z,\gamma)\) where both ''s and z are empty strings. The extended Veblen functions are defined as follows: *\(\varphi(\gamma)=\omega^\gamma\), *\(\varphi(z,s,\gamma)=\varphi(s,\gamma)\), * if \(\alpha_{n+1}>0\), where \(n\geq 0\), then \(\varphi(s,\alpha_{n+1}, z, \gamma)\) denotes the \(1+\gamma\)th common fixed point of the functions \(\xi \mapsto \varphi(s, \beta, \xi,z)\) for each \(\beta<\alpha_{n+1}\). Every non-zero ordinal \(\alpha\) less than the small Veblen ordinal (SVO) can be uniquely written in normal form for the finitary Veblen function: \( \alpha=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)\) where *\(\varphi(s_1)\geq\varphi(s_2)\geq\cdots\geq\varphi(s_k)\), *\(s_m\) is an arbitrary string of ordinal variables \(\alpha_{m,1}, \alpha_{m,2},...,\alpha_{m,n_m}\) where \(m \in \{1,...,k\}\) * \(\alpha_{m,1}>0\) and \(\alpha_{m,i} <\varphi(s_m)\) for \(m \in \{1,...,k\}\) and \(i \in \{1,..,n_m\}\), * \(k, n_1,...,n_k\) are positive integers. Fundamental sequences for limit ordinals of finitary Veblen function For limit ordinals \(\alpha0\) in string of arguments of the Veblen function. For example: \(\begin{pmatrix}\alpha_1 & \alpha_2 & \alpha_3 \\8 & 5 & 0 \end{pmatrix}=\varphi(\alpha_1,0,0,\alpha_2,0,0,0,0,\alpha_3)\). If a limit ordinal \(\alpha\) is written in next normal form \(\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix}+\begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix}+\cdots+\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\), where *\(\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix} \geq \begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix} \geq \cdots \geq \begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\), *\(\alpha_{m,i}<\begin{pmatrix} \alpha_{m,1} & \cdots &\alpha_{m,n_m} \\ \beta_{m,1} & \cdots & \beta_{m,n_m} \end{pmatrix}\) for all \(i \in \{1,...,n_m\}\), \(m \in \{1,...,k\}\), *\(\beta_{m,i}<\begin{pmatrix} \alpha_{m,1} & \cdots &\alpha_{m,n_m} \\ \beta_{m,1} & \cdots & \beta_{m,n_m} \end{pmatrix}\) for all \(i \in \{1,...,n_m\}\), \(m \in \{1,...,k\}\), *\(\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\) is a limit ordinal, *\(k,n_1,...,n_k\) are positive integers, then \(\alphan=\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix}+\begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix}+\cdots+\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}n\) (2). If \(n_k=1\) and \(\beta_{k,n_k}=0\) then the last term (LT) in expression (2) is equal to \(\begin{pmatrix}\alpha_{k,1} \\ 0 \end{pmatrix}=\varphi(\alpha_{k,1})=\omega^{\alpha_{k,1}}\) and should use rule for single-argument form to assign fundamental sequences (FS) for LT, otherwise use rules 3.1-3.9 to assign FS for LT: 3.1) \(\begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}0=0\) and \(\begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}n+1=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}n \\ \cdots & \beta+1 & \beta \end{pmatrix}\), 3.2) \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}0=\begin{pmatrix}\cdots & \alpha+1 & \gamma \\ \cdots & \beta+1 & 0 \end{pmatrix}+1\) and \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}n+1=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}n \\ \cdots & \beta+1 & \beta \end{pmatrix}\), 3.3) \(\begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta & 0 \end{pmatrix}n=\begin{pmatrix}\cdots & \alpha & \gamma n \\ \cdots & \beta & 0 \end{pmatrix}\) if \(\gamma\) is a limit ordinal, 3.4) \(\begin{pmatrix}\cdots & \alpha & \\ \cdots & \beta+1 \end{pmatrix}n=\begin{pmatrix}\cdots & \alpha n & \\ \cdots & \beta+1 \end{pmatrix}\) if \(\alpha\) is a limit ordinal, 3.5) \(\begin{pmatrix}\cdots & \alpha & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}n=\begin{pmatrix}\cdots & \alpha n & \begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta+1 & 0 \end{pmatrix}+1 \\ \cdots & \beta+1 & \beta \end{pmatrix}\) if \(\alpha\) is a limit ordinal, 3.6) \(\begin{pmatrix}\cdots & \alpha+1\\ \cdots & \beta\end{pmatrix}n=\begin{pmatrix}\cdots & \alpha & 1 \\ \cdots & \beta& \beta n\end{pmatrix}\) if \(\beta\) is a limit ordinal, 3.7) \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta & 0 \end{pmatrix}n=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 & \gamma \\ \cdots & \beta & 0 \end{pmatrix}+1 \\ \cdots & \beta & \betan \end{pmatrix}\) if \(\beta\) is a limit ordinal, 3.8) \(\begin{pmatrix}\cdots & \alpha\\ \cdots & \beta\end{pmatrix}n=\begin{pmatrix}\cdots & \alpha n \\ \cdots & \beta \end{pmatrix}\) if \(\alpha\) and \(\beta\) are limit ordinals, 3.9) \(\begin{pmatrix}\cdots & \alpha & \gamma+1 \\ \cdots & \beta & 0 \end{pmatrix}n=\begin{pmatrix}\cdots & \alpha n& \begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta & 0 \end{pmatrix}+1 \\ \cdots & \beta & \beta n \end{pmatrix}\) if \(\alpha\) and \(\beta\) are limit ordinals. The limit of this notation is large Veblen ordinal (LVO): *\(LVO0=0\), *\(LVOn+1=\begin{pmatrix}1 \\ LVOn \end{pmatrix}\). Comparison with theta function The extended Veblen function and Bird/Feferman theta-functions up to SVO are connected by the next expression: \( \theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma) = \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\) and \(\theta(\alpha, 0)\) can be abbreviated as \(\theta(\alpha)\). In this terms \(SVO=\theta(\Omega^\omega)\). For transfinary Veblen function for example: \(\begin{pmatrix} 1\\ \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\end{pmatrix}=\theta(\Omega^{\theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma)})\), \(\begin{pmatrix} 1\\\begin{pmatrix} 1\\ \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\end{pmatrix}\end{pmatrix}=\theta(\Omega^{\theta(\Omega^{\theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma)})})\) and so on. In this terms \(LVO=\theta(\Omega^\Omega)\). According to Hyp cos' estimation, the growth rate of the function of fast-growing hierarchy \(f_{\begin{pmatrix}\omega \\ \omega \end{pmatrix}}(n) \) is less than or equal to the growth rate of Harvey Friedman's TREE(n) function. The fast-growing hierarchy function indexed by the Large Veblen ordinal, \(f_{LVO}(10)\), is near to the lowest estimation of Bowers' meameamealokkapoowa oompa. Sources See also Category:Functions Category:Transfinite ordinals